package LiKouBrushQuestions;

import java.util.Scanner;
import java.util.Stack;

public class June_27 {
    public static void main(String[] args) {
        System.out.println("虽千万难，吾亦往矣");
    }
}

//合并两个有序链表
class ListNodeOne {
    int val;
    ListNode next;

    ListNodeOne() {
    }

    ListNodeOne(int val) {
        this.val = val;
    }

    ListNodeOne(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class SolutionListNode {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 != null) {
            return l1;
        }
        ListNode listNode = l1.val < l2.val ? l1 : l2;
        listNode.next = mergeTwoLists(listNode.next, l1.val >= l2.val ? l1 : l2);
        return listNode;
    }
}

class Solution1 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode ans = null;
        if (l1.val < l2.val) {
            ans = l1;
            l1 = l1.next;
        } else {
            ans = l2;
            l2 = l2.next;
        }
        ListNode root = ans;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                root.next = l1;
                l1 = l1.next;
                root = root.next;
            } else {
                root.next = l2;
                l2 = l2.next;
                root = root.next;
            }
        }
        if (l1 == null) root.next = l2;
        else root.next = l1;
        return ans;
    }
}


/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 *
 * @author 23737
 * @time 6.27
 */
//两个栈来实现队列
class CQueue {

    //定义两个栈用来实现队列
    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public CQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void appendTail(int value) {
        inStack.push(value);
    }

    public int deleteHead() {
        if (outStack.empty() && inStack.empty()) {
            return -1;
        }
        if (!outStack.empty()) {
            return outStack.pop();
        }
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
        return outStack.pop();
    }
}

/**
 * @time 6.27
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 */
class Fib {
    public int fib(int n) {
//        int a = 1;
//        int b = 0;
//        if (n == 0) {
//            return 0;
//        } else if (n == 1) {
//            return 1;
//        } else {
//            return (fib(n-1)+fib(n-2))%1000000007;
//        }
        if (n <= 1)
            return n;
        int pre2 = 0, pre1 = 1;
        int fib = 0;
        for (int i = 2; i <= n; i++) {
            fib = (pre2 + pre1) % 1000000007;
            pre2 = pre1;
            pre1 = fib;
        }
        return fib;
    }
}

/**
 * @time 6.27
 * 数组中重复的元素
 */
class SolutionArray {
    public int findRepeatNumber(int[] nums) {
        //这道题的解法是真的很巧妙，理解思想
        int arrs[] = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arrs[nums[i]]++;
            if (arrs[nums[i]] > 1) {
                return nums[i];
            }
        }
        return -1;
    }
}

/**
 * @time 6.28
 * 青蛙跳台阶
 */
//其实就是斐波拉契数列
class SolutionFib {
    public int numWays(int n) {
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int pre = 1;
        int next = 2;
        for (int i = 2; i < n; i++) {
            int temp = next;
            next = (pre + next) % 1000000007;
            pre = temp;
        }
        return next;
    }
}





